In typical database systems, users store, update, and retrieve information by interacting with user applications (“clients”). The clients respond to the user's interaction by submitting commands to a database application (a database management system/a “database server”) responsible for maintaining the database. The database server responds to the commands by performing the specified actions on the database. To be correctly processed, the commands must comply with the database language that is supported by the database server. One popular database language is known as Structured Query Language (SQL).
One common configuration of a database is one made up of various tables with each table being formed of rows and columns of information. The information stored across one row in the table would make up one record and the fields of the record would be columns in the table. In other words, the table would contain rows of individual records and columns of record fields. Because one record may contain more than one field of information, the information of the field would make up the columns of the database table. Other database configurations are known in the art.
An index is commonly used by database management programs to provide quick and efficient associative access to a table's records. Indexes are commonly configured in a B-Tree structure which includes a root node with many levels of nodes branching from the root node. The information contained in these nodes may include pointers which point to the nodes at the next level of the tree or it may include pointers which point to one or more records stored in the database. These pointers include additional key record information which may reference the records stored in the database. The record keys are stored in an ordered form throughout the nodes at the various branches of the tree. For example, an index tree may exist for selected attributes such as an alphabetic listing of employee names.
To support dynamically changing attributes, prior systems created a b-tree for each attribute. Another approach included having one b-tree that is created on a name-value pairs or all attributes. In either of these approaches, a query processor had to decide which search condition should use a b-tree, then scan the b-trees, combine the results and perform filtering, if necessary, to obtain a final answer to the query.
Prior solutions tend to be costly when intermediate results include large amounts of data. Much of the cost is associated with sorting overhead for combining intermediate results and I/O cost for filtering. This is typically the case when a query includes multiple numeric range conditions that may result in large amounts of intermediate data before a final result is found.
The present invention provides a new and useful method and system of indexing and searching that addresses the above problems.